
using System;

using System.Collections.Generic;
using UnityEngine;

public class Solution : MonoBehaviour
{

    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }
    void Start()
    {
        int[] nums = { 5, 5, 6, 6, 7, 8, 1, 2, 3, 4, 5 };
        //Debug.Log(MinArray(nums));

    }






    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int x) { val = x; }
    }

    public ListNode MergeTwoLists(ListNode l1, ListNode l2)
    {

        ListNode new_list = new ListNode(0);
        ListNode flg_list = new ListNode(0);
        //todo 两节点一个 的情况
        flg_list = new_list;
        while (l1 != null && l2 != null)
        {
            if (l1.val >= l2.val)
            {
                new_list.next = l2;
                l2 = l2.next;
            }
            else
            {
                new_list.next = l1;
                l1 = l1.next;
            }
            new_list = new_list.next;

        }
        new_list.next = (l1 != null) ? l1 : l2;
        return flg_list.next;
    }

    //第二题我的解答：
    //1.暴力破解  2.链表一存入字典 在字典里逐步遍历链表二  （字典本质是哈希表，而哈希表的查找 containsKey()的时间复杂度是O(1)）
    // 为什么数组的时间复杂度是O(1),
    //  因为内存被设计成访问任一位置时间都是一样的, 
    //  而且非常块, 内存的大小对此并无影响.数组基于顺序的内存地址, 
    //  所以数组访问元素时间复杂度是O(1), 即数组的大小对此并无影响.哈希表的设计可以基于数组, 
    //  所以哈希表查询的平均时间复杂度为O(1).

    //官方解答：双指针：指针A遍历第一个链表 当下一个节点为空再去指向第二个链表头节点开始遍历，指针B从链表二开始同理，
    //设公共长度为c 不公共长度分别为 a,b，这样遍历到最后就是 a+c+b=b+c+a；得到共同节点
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
    {
        if (headA == null || headB == null)
        {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB)
        {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }




}